UVa/10167 - Birthday cake/10167.cpp

   1 #include <iostream>
   2 #include <vector>
   3 #include <algorithm>
   4
   5 using namespace std;
   6
   7 int n;
   8
   9 struct point{
  10   int x, y;
  11   point() {}
  12   point(const int &X, const int &Y) : x(X), y(Y) {}
  13 };
  14
  15 struct line{
  16   int a, b;
  17   line() {}
  18   line(const int &A, const int &B) : a(A), b(B) {}
  19 };
  20
  21
  22 //Returns positive if p is to the left of line l
  23 //Returns negative if p is to the right of line l
  24 //Returns zero if p is colineal with line l
  25 int cross(const point &p, const line &l){
  26   point q;
  27   q.x = l.b;
  28   q.y = -l.a;
  29
  30   return (p.x*q.y - q.x*p.y);
  31 }
  32
  33 bool check(const vector<point> &c, const line &l){
  34   int left = 0, right = 0;
  35   for (int i=0; i<2*n; ++i){
  36     int t = cross(c[i], l);
  37     left  += (t>0);
  38     right += (t<0);
  39   }
  40   return (left == n && right == n);
  41 }
  42
  43
  44 int main(){
  45   while (cin >> n && n){
  46     vector<point> cherry(2*n);
  47     for (int i=0; i<2*n; ++i){
  48       cin >> cherry[i].x >> cherry[i].y;
  49     }
  50
  51     bool found = false;
  52     for (int i=-500; i<=500 && !found; ++i){
  53       for (int j=-500; j<=500 && !found; ++j){
  54         if (check(cherry, line(i, j))){
  55           cout << i << " " << j << endl;
  56           found = true;
  57         }
  58       }
  59     }
  60
  61   }
  62
  63   return 0;
  64 }